package org.ayachinene.leetcode.problems;

import org.ayachinene.leetcode.structure.TreeNode;

public class P1145 {

    static class Solution {
        public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
            TreeNode selected = getNode(root, x);
            int leftSize = getSize(selected.left);
            if (leftSize > n / 2) {
                return true;
            }
            int rightSize = getSize(selected.right);
            if (rightSize > n / 2) {
                return true;
            }
            int otherSize = n - 1 - leftSize - rightSize;
            return otherSize > n / 2;
        }

        private TreeNode getNode(TreeNode root, int val) {
            if (root == null) {
                return null;
            }

            if (root.val == val) {
                return root;
            }

            TreeNode res = getNode(root.left, val);
            return res == null ? getNode(root.right, val) : res;
        }

        private int getSize(TreeNode root) {
            if (root == null) {
                return 0;
            }

            return getSize(root.left) + getSize(root.right) + 1;
        }
    }
}
